문제 설명
빙고는 NxN 크기의 게임 보드 칸에 1부터 NxN까지의 자연수를 중복 없이 하나씩 적은 후 숫자를 하나씩 지워나가는 게임입니다. 이때, 가로, 세로, 대각선 방향으로 한 줄에 적힌 숫자를 모두 지울 경우 빙고를 1개 만들었다고 합니다. 다음은 4X4 크기의 게임 보드를 이용해 게임을 진행한 예시입니다.
위와 같이 각 칸에 숫자가 적혀 있을 때, 위 게임 보드에서 순서대로 지운 숫자가 [14,3,2,4,13,1,16,11,5,15]인 경우 아래와 같이 빙고 3개가 만들어집니다.
빙고 게임 보드에 적힌 숫자가 담겨있는 배열 board, 게임 보드에서 순서대로 지운 숫자가 들어있는 배열 nums가 매개변수로 주어질 때, board에서 nums에 들어있는 숫자를 모두 지우면 몇 개의 빙고가 만들어지는지 return하도록 solution함수를 완성해주세요.
제한사항
- board는 게임 보드 칸에 적힌 숫자를 뜻하는 NxN크기의 2차원 배열이며, N은 2 이상 500이하의 자연수입니다.
- board의 각 칸에는 1 이상 NxN이하의 자연수가 중복 없이 하나씩 들어있습니다.
- nums는 board에서 지울 숫자가 들어있는 배열이며, 길이는 1 이상 NxN이하입니다.
- nums에 들어있는 숫자는 1 이상 NxN이하의 자연수이며, 중복된 수가 들어있지 않습니다.
입출력 예
| board | nums | result |
|---|---|---|
| [[11,13,15,16],[12,1,4,3],[10,2,7,8],[5,14,6,9]] | [14,3,2,4,13,1,16,11,5,15] | 3 |
| [[6,15,17,14,23],[5,12,16,13,25],[21,4,2,1,22],[10,20,3,18,8],[11,9,19,24,7]] | [15,7,2,25,9,16,12,18,5,4,10,13,20] | 2 |
입출력 예 설명
입출력 예 #1 문제의 예시와 같습니다.
입출력 예 #2
다음 그림과 같이 2개의 빙고가 만들어집니다.
나의 풀이
첫번째 풀이
소스
def check_bingo_horizontal(N, row, board):
for i in range(N):
if board[row][i] != -1:
return False
return True
def check_bingo_vertical(N, col, board):
for i in range(N):
if board[i][col] != -1:
return False
return True
def check_bingo_diagonal(N, board):
for i in range(N):
if board[i][i] != -1:
return False
return True
def check_bingo_diagonal_reverse(N, board):
max_idx = N - 1
for i in range(N):
if board[i][max_idx - i] != -1:
return False
return True
def solution(board, nums):
answer = 0
bingo_hashboard = {}
N = len(board)
for row in range(N):
for col in range(N):
bingo_hashboard[board[row][col]] = (row, col)
for num in nums:
row, col = bingo_hashboard[num]
board[row][col] = -1
# 가로 체크
if check_bingo_horizontal(N, row, board):
answer += 1
# 세로 체크
if check_bingo_vertical(N, col, board):
answer += 1
# 대각선 체크 - 대각선 체크는 대각선 가능 유무도 판단한다
if row == col and check_bingo_diagonal(N, board):
answer += 1
# 역 대각선 체크 - 대각선 체크는 대각선 가능 유무도 판단한다
if row + col == N - 1 and check_bingo_diagonal_reverse(N, board):
answer += 1
return answer설명
- 일단, 빙고를 위한 숫자값이 들어왔을 때 (nums 순회) 그 해당 숫자가 어느위치에 있는지 빠르게 찾아가는것이 관건. (중복된 수가 들어오지 않기 때문에 따로 예외처리 할 필요는 없다.)
- 그래서 bingo_hashboard라고 딕셔너리를 만들어 해당 값에 대한 위치정보를 담아둔다. {14:(0,3), 18:(3,3)…}
- nums를 순회하면서 각 값에대한 해당 위치를 딕셔너리를 이용해 빠르게 찾고, 해당 위치값을 기반으로 빙고가 되었는지 체크한다.
- 각 빙고를 체크하는 것은 함수화 시켜서 가로, 세로, 대각선, 역대각선 이렇게 처리하였다.
결과
통과
리뷰
- 전체적으로 잘 작성하셨습니다. :) 실수하신 곳 한 부분만 수정하면 될 것 같습니다.
- 시간복잡도는 전처리 하는 부분이 n^2이기 때문에 O(n^2)이 맞습니다. :)
해당 부분은
for루프 바깥으로 빼도 정상 동작하는 것 같습니다. :)for num in nums: row, col = bingo_hashboard[num] board[row][col] = -1 # 가로 체크 if check_bingo_horizontal(N, row, board): answer += 1 # 세로 체크 if check_bingo_vertical(N, col, board): answer += 1 # 대각선 체크 - 대각선 체크는 대각선 가능 유무도 판단한다 if check_bingo_diagonal(N, board): answer += 1 # 역 대각선 체크 - 대각선 체크는 대각선 가능 유무도 판단한다 if check_bingo_diagonal_reverse(N, board): answer += 1
스터디 리더의 풀이
def solution(board, nums):
n = len(board) # board의 길이
nums = set(nums)
row_list = [0] * n
col_list = [0] * n
left_diagonal = 0
right_diagonal = 0
for i in range(n): # O(n)
for j in range(n): # O(n)
if board[i][j] in nums: # O(1)
board[i][j] = 0
row_list[i] += 1
col_list[j] += 1
if i == j:
left_diagonal += 1
if n - 1 - i == j:
right_diagonal += 1
answer = 0
answer += sum([1 for i in row_list if i == n]) # 세로
answer += sum([1 for i in col_list if i == n]) # 가로
answer += 1 if left_diagonal == n else 0 # 왼쪽 대각선
answer += 1 if right_diagonal == n else 0 # 오른쪽 대각선
return answer분석
- 스터디 리더님의 풀이는 나처럼 nums를 순회하는 것이 아니라 애초에 정답을 처음부터 다 기록을 해두는 아이디어이다.
- 빙고판을 순회하면서 불려진 값이 있으면 해당 값을 체크하는데, 여기서 rowlist와 collist를 각각 따로두어서 나온 개수만큼 관리를 하고, 이 rowlist, collist가 n만큼 개수가 되면 빙고가 완성되었다고 보는 방식.
- 비슷한 방식으로 leftdiagonal과 rightdiagonal의 변수를 두어서 대각선의 나온 개수값을 체크한다.
- 그래서 이렇게 빙고판을 다 돌고난 다음, 각각 rowlist와 collist, leftdiagonal, rightdiagonal을 통해 빙고 개수를 체크.
